import java.util.*;

class Solution {
    public int minPushBox(char[][] grid) {
        Queue<State> queue = new PriorityQueue<>();
        //五维: 1. 距离 2.Person.x 3. Person.y 4. Box.x 5. Box.y
        int row = grid.length;
        int col = grid[0].length;

        int[] posOfPerson = new int[2];
        int[] posOfBox = new int[2];

        for(int i = 0; i < row; i++){
            for(int j = 0 ; j < col; j++){
                if(grid[i][j] == 'S'){
                    grid[i][j] = '.';
                    posOfPerson[0] = i;
                    posOfPerson[1] = j;
                }
                if(grid[i][j] == 'B'){
                    grid[i][j] = '.';
                    posOfBox[0] = i;
                    posOfBox[1] = j;
                }
            }
        }

//        Integer[] temp = new Integer[]{0, posOfPerson[0], posOfPerson[1], posOfBox[0], posOfBox[1]};
        queue.add(new State(0, posOfPerson[0], posOfPerson[1], posOfBox[0], posOfBox[1]));

        Map<Integer[], Integer> distance = new HashMap<>();
        distance.put(new Integer[]{posOfPerson[0], posOfPerson[1], posOfBox[0], posOfBox[1]}, 0);
        int[] vx = {0,0,-1,1};
        int[] vy = {1,-1,0,0};
        while(!queue.isEmpty()){

            System.out.println("queue.size() = " + queue.size());

            State res = queue.poll();

            for(int i = 0; i < 4; i++){
                //挪动人
                Integer[] nextPerson = {res.boxX + vx[i], res.boxY + vy[i]};
                if(nextPerson[0] < 0 || nextPerson[0] >= row || nextPerson[1] < 0 || nextPerson[1] >= col || grid[nextPerson[0]][nextPerson[1]] == '#'){
                    continue;
                }

                Integer[] nextBox = {res.personX, res.personY};
                int d = res.distance;//箱子挪动的距离

                if(nextPerson[0] == res.personX && nextPerson[1] == res.personY){
                    System.out.println("nextBox is changed!\n");
                    nextBox[0] = res.personX + vx[i];
                    nextBox[1] = res.personY + vy[i];
                    if(nextBox[0] < 0 || nextBox[0] >= row || nextBox[1] < 0 || nextBox[1] >= col || grid[nextBox[0]][nextBox[1]] == '#'){
                        continue;
                    }
                    //挪动的距离增加
                    d++;
                }

                System.out.println("nextBox[0] = " + nextBox[0]);
                System.out.println("nextBox[1] = " + nextBox[1]);


                if(grid[nextBox[0]][nextBox[1]] == 'T'){
                    return d;
                }
                //如果已经存在该路径，那么继续查找
                if(distance.containsKey(new Integer[]{nextPerson[0], nextPerson[1], nextBox[0], nextBox[1]})){
                    continue;
                }
                //保存距离值
                distance.put(new Integer[]{nextPerson[0], nextPerson[1], nextBox[0], nextBox[1]}, d);

//                Integer[] temp1 = new Integer[]{d, nextPerson[0], nextPerson[1], nextBox[0], nextBox[1]};
                queue.add(new State(d, nextPerson[0], nextPerson[1], nextBox[0], nextBox[1]));
            }
        }
        return -1;
    }

    class State implements Comparable<State>{
        public int distance;
        public int personX;
        public int personY;
        public int boxX;
        public int boxY;

        public State(int distance, int personX, int personY, int boxX, int boxY) {
            this.distance = distance;
            this.personX = personX;
            this.personY = personY;
            this.boxX = boxX;
            this.boxY = boxY;
        }

        @Override
        public int compareTo(State o) {
            return this.distance - o.distance;
        }
    }
}